package leetcode;

import java.util.Arrays;

/**
 *
 * 递归回溯
 */
public class HuiSu {

    public static int CoinChange(int[] coins, int K){
        //这里传入一个数组记录count【k】的最优解，如果有最优解不用重复计算直接返回
        int[] count = new int[K+1];
        Arrays.fill(count,-666);
        return dp(coins,K,count);
    }
    //递归求最优解，从上至下
    private  static  int dp(int[] coins, int K , int [] count) {
        //递归的终止条件
        //当遇到 K 小于等于 0 时停止递归并回溯结果
        if (K==0) return 0;
        //返回-1表示无法兑换
        if (K < 0) return -1;
        // 查备忘录，防止重复计算,如果之前递归已经求出某个值的最优解，则不用重复递归了
        if (count[K] != -666)
            return count[K];
        int res = Integer.MAX_VALUE;//返回结果初始化为最大值
        //遍历所有的面值
        //coin是coins数组的元素
        for (int coin : coins){
            //针对coin值开始递归
            //sub是子问题的结果，即K - coin的最优解
            //递归调用的过程中目标金额K会不断减小
            int sub = dp(coins,K-coin,count);
            //如果返回的是-1，说明coin面值的纸币无法兑换，不选择这个coin
            if (sub==-1){
                continue;
            }
            //通过比较选择最合适的面值得出的最小值
            res = Math.min(res,sub+1);
        }
        //将最优解存入备忘录中
        count[K] = res==Integer.MAX_VALUE ? -1 : res;
        return count[K];
    }

    public static void main(String[] args) {
        int[] coins = new int[]{1,2,5,10,20,50,100};
        int res = CoinChange(coins,99);
        System.out.println(res);
    }
}
